package com.company;

/**
 * @author zhf
 * @date 2021/10/22
 */

import java.util.Deque;
import java.util.LinkedList;

/**
 * 最长的有效括号
 *
 * 使用堆栈来实现
 */
public class Longestvalid {
    public static void main(String[] args) {
        String s = ")()())";
        Longestvalid longestvalid = new Longestvalid();
        int ans = longestvalid.longestValidParentheses(s);
        System.out.println(ans);
    }

    public int longestValidParentheses(String s) {

        /*
        Deque:双端队列，堆栈；
        java中Stack类已经过时，官方推荐使用Deque代替Stack；
         */

        //使用堆栈实现
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        int ans = 0;
        /**
         * 从前往后遍历字符串，遇到“（”将其入栈，遇到“）”，将栈顶元素弹出
         * 如果栈中为空，将当前字符入栈
         */
        for (int i = 0; i <s.length() ; i++) {
            if (s.charAt(i) == '('){
                stack.push(i);
            }else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                }else {
                    ans = Math.max(ans,i-stack.peek());
                }
            }

        }
        return ans;
    }
}
